/***
 * A/B型互斥锁 应用于引用计数
 * 两个互斥量: 在同时使用两个互斥量时,总是让它们以相同的顺序加锁,这样可以避免死锁.
 * P323-325
 */

#include "apue.h"
#include <pthread.h>

#define NHASH 29
#define HASH(id) (((unsigned long)id) % NHASH)

// 这个是全局的, 多线程时需要 加锁
struct foo *fh[NHASH]; //散列表

//常量PTHREAD_MUTEX_INITIALIZER只适用于静态分配的互斥量(全局的互斥量)
pthread_mutex_t hashlock = PTHREAD_MUTEX_INITIALIZER; // 用来保护 fh[]

struct foo
{
    int f_count;
    pthread_mutex_t f_lock;
    int f_id;
    struct foo *f_next; /* protocted by hashlock */
    /* ... more stuff here ... */
};

/* 
    每allocate一个object,
    就将其放到 散列表 ( struct foo *fh[NHASH] ) 中

    散列表: type* hash[number] , 相当于是一堆篮子
    每个[index]是一个list , 相当于是第[index]个篮子
    每个list上,挂着一串对象 , 通过next指针进行遍历
*/
struct foo *foo_alloc(int id) /* allocate the object */
{
    struct foo *fp;
    int idx;
    if ((fp = malloc(sizeof(struct foo)) != NULL))
    {
        fp->f_count = 1;
        fp->f_id = id;
        if (pthread_mutex_init(&fp->f_lock, NULL) != 0)
        {
            free(fp);
            return (NULL);
        }

        idx = HASH(id);
        pthread_mutex_lock(&hashlock); //操作 哈系表/散列表 的时候, 使用锁hashlock 
        // 因为多个线程可能malloc了多个object 
        //  此处hashlock 既防止 多个线程中的fp指向同一个fh[[idx] ,  也防止 fh[idx]指向多个fp
        fp->f_next = fh[idx];
        fh[idx] = fp;
        pthread_mutex_lock(&fp->f_lock); // 操作某个具体object时, 使用锁f_lock
        pthread_mutex_unlock(&hashlock);
        /* ... continue initialization ... */
        pthread_mutex_unlock(&fp->f_lock);
    }
    return (fp);
}

void foo_hold(struct foo *fp) /*add a reference to the object */
{
    pthread_mutex_lock(&fp->f_lock);
    fp->f_count++;
    pthread_mutex_unlock(&fp->f_lock);
}

/*
    查找到某个具体的 object 
    对其中的引用计数 +1 
    然后返回 指向这个object的指针
*/
struct foo *foo_find(int id) /* find an existing object */
{
    struct foo *fp;

    /*
        每次遍历 散列表 时加锁 hashlock
            操作 散列表中的某个object时,加锁 ; 操作完毕,解锁
        然后对hashlock解锁
    */
    pthread_mutex_lock(&hashlock);                  //操作 哈系表/散列表 的时候, 使用锁hashlock
    for (fp = fh[HASH(id)]; fp != NULL; fp->f_next) // 首先用fp指针,指向第[idx]号篮子 , 然后遍历篮子中的object , 找到我们的object然后操作.
    {
        if (fp->f_id == id)
        {
            foo_hold(fp);
            break;
        }
    }
    pthread_mutex_lock(&hashlock);

    return (fp);
}

void foo_rele(struct foo *fp) /* release a reference to the object*/
{
    struct foo *tfp;
    int idx;

    // 细粒度锁 !!!
    //先加细粒度锁,然后if ； 比 直接加粗粒度锁,然后if --> 对性能影响最小
    pthread_mutex_lock(&fp->f_lock); // 操作某个具体object时, 使用锁f_lock
    if (fp->f_count == 1)            /* last reference */
    {
        pthread_mutex_unlock(&fp->f_lock);

        //保证AB型锁的 加锁顺序 !!!
        // 对于A/B型锁,要保证加锁的顺序,这样就可以避免AB型死锁
        pthread_mutex_lock(&hashlock); // 因为有可能要操作fh[]和f_next,所以要先对hashlock加锁
        pthread_mutex_lock(&fp->f_lock); // 因为需要操作具体的object,所以需要对f_lock加锁
        
        // recheck !!!
        /* need to recheck the condition */
        if (fp->f_count != 1) // 因为上面两个f_lock之间有窗口期, 所以必须 recheck
        {
            fp->f_count--;
            pthread_mutex_unlock(&fp->f_lock);
            pthread_mutex_unlock(&hashlock);
            return;
        }

        /* remove from list */ // 删除object
        idx = HASH(fp->f_id);
        tfp = fh[idx];
        if (tfp == fp)
        {
            fh[idx] = fp->f_next;
        }
        else
        {
            while (tfp->f_next != fp)
                tfp = tfp->f_next;
            tfp->f_next = fp->f_next;
        }

        pthread_mutex_unlock(&hashlock);
        pthread_mutex_unlock(&fp->f_lock);

        pthread_mutex_destroy(&fp->f_lock);
        free(fp);
    }
    else
    {
        fp->f_count--;
        pthread_mutex_unlock(&fp->f_lock);
    }
}